package cn.ycc1;

/**
 * 八皇后问题
 * 回溯 + 剪枝
 * @author ycc
 * @date 2024/6/4
 * 利用大模型生成工具帮助自己写代码学习
 * 降低学习数据结构和算法，设计模式的动手难度
 * 有助于提示自己代码的逻辑，并加深对算法的理解和思考
 * 根据提示引导自己了解学习优秀的写法，开阔视野
 * 根据多种解法，通过一道题，联系多种算法思想
 * 有了新工具如大模型及后来的工具，可以优化以前数据结构和算法的学习，
 * 以前复杂的理解，有了新工具，就便捷简单一些了。
 */
public class EightQueens {
    private static final int SIZE = 8;
    private static int[] queens = new int[SIZE]; // 存储每一行放置的列
    private static int count = 0;

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.placeQueens(0);
        System.out.println("共有摆法 " + count + " 种！");
    }

    private void placeQueens(int row) {
        // 结束条件 递归出口
        if (row == SIZE) {
            ++count;
//            print();
            printQueens();
            return;
        }
        for (int col = 0; col < SIZE; ++col) {
            queens[row] = col;
            if (isValid(row, col)) {
                placeQueens(row + 1);
            }
        }
    }

    /**
     * 判断是否可以放置皇后
     * @param row
     * @param col
     * @return
     */
    private boolean isValid(int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (queens[i] == col || Math.abs(row - i) == Math.abs(col - queens[i])) {
                return false;
            }
        }
        return true;
    }

    private void printQueens() {
        System.out.println("第" + count + "种摆法：");
        for(int row = 0; row < SIZE; ++row) {
            for(int col = 0; col < SIZE; ++col) {
                if (queens[row] == col) {
                    System.out.print("Q ");
                } else {
//                    System.out.print("- ");
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    private void print() {
        for (int i = 0; i < SIZE; ++i) {
            System.out.print(queens[i] + " ");
        }
        System.out.println();
    }

}
